The invention relates to the field of asymmetric digital subscriber line (ADSL) communication systems. More specifically, the invention relates to a system and method for encoding signals applied to ADSL.
Channel coding methods are used in order to design reliable digital communication systems. Although channel coding improves error performance through the mapping of input sequences into code sequences, this adds redundancy and memory to the transmission. Shannon's Theorem holds that small error rates are achievable provided that the rate of transmission is less than the capacity of the channel.
In the early 1990's, a very powerful channel coding scheme was developed which used concepts related to block and trellis codes. The encoding scheme used simple convolutional codes separated by interleaving stages to produce generally low rate block codes. Decoding was performed by decoding the convolutional encoders separately using a “soft” output Viterbi algorithm and sharing bit reliability information in an iterative manner. This new coding scheme was called “Turbo Coding” and it was found to be capable of near Shannon capacity performance as described in C. Berrou and A. Glavieux, “Near Optimum Error Correcting Coding And Decoding: Turbo-Codes”, IEEE Trans. Commun., vol. COM-44, No. 10, October 1996, pp. 1261–1271.
In general, a turbo encoder is a combination of two simple encoders where the input is a block of M information bits. The two encoders generate parity symbols using simple recursive convolutional encoders each with a small number of states. The information bits are also transmitted uncoded. A key innovation of turbo encoders was the use of an interleaver which permutes the original M information bits before input to the second encoder. The permutation is generally such that input sequences for which the first encoder produces low-weight code-words will typically cause the second encoder to produce high-weight code-words. Thus, even though the constituent codes may be individually weak, the combination code is powerful. This resulting code has features that are similar to a random block code with M information bits. Random block codes are known to achieve Shannon-limit performance as M increases but with a corresponding increase in decoder complexity.
Turbo codes may achieve the performance of random codes (for large M) using an iterative decoding algorithm based on simple decoders that are individually matched to the constituent codes. In a typical turbo decoder, each constituent decoder generally sends a posteriori likelihood estimates of the decoded bits to the second decoder and uses the corresponding estimates from the second decoder as a priori likelihood estimates. The decoders generally use the maximum a posteriori (MAP) bitwise decoding algorithm which requires the same number of states as the well-known Viterbi algorithm. The turbo decoder iterates between the outputs of the two constituent decoders until reaching satisfactory convergence. The final output is a “hard” quantized version of the likelihood estimates of either of the decoders.
As turbo codes have a near Shannon limit, error correcting performance, they are of potential use in a wide range of telecommunications applications. As mentioned, turbo codes were originally proposed for binary modulation using two binary convolutional component codes separated by an interleaver. For moderate QAM (quadrature amplitude modulation) constellation modulation, bit-level turbo coded QAM and symbol-level turbo TCM (trellis coded modulation) have been proposed as described in P. Robertson and T. Worz, “Bandwidth-Efficient Turbo Trellis-Coded Modulation Using Punctured Component Codes”, IEEE J-SAC, vol. 16, No. 2, February 1998, pp. 206–218; S. L. Goff, A. Glavieux and C. Berrou, “Turbo-Codes and High Spectral Efficiency Modulation”, IEEE ICC94, pp. 645–649, 1994; and “New Proposal of Turbo Codes for ADSL Modems”, ITU Standard Contribution, Study Group 15/4, BA-020R1, Antwerp, Belgium, Jun. 19–23, 2000.
Typically, bit-level turbo coded QAM combines the binary turbo codes with large constellation modulation using Gray mapping, whereas symbol-level turbo TCM uses TCM codes as component codes that are separated by a symbol-level interleaver.
A problem arises in the deployment of turbo codes in ADSL (asymmetric digital subscriber line) communication systems where these codes are combined with very large modulation constellations. These constellations may be as large as 215 (32768) QAM symbols. For conventional bit-level turbo coded QAM using Gray mapping, the de-mapper (which calculates the soft information bits from the received constellation signal) requires an excessive number of computations. In addition, the turbo decoder's complexity (i.e., length) is proportional to the number of bits transmitted in one constellation symbol. Therefore, the overall receiver becomes very complicated. For symbol-level turbo TCM using two-dimensional or four-dimensional set partitioning mapping, the turbo decoder's length is independent of the number of bits transmitted in one constellation symbol, but its de-mapper still requires an excessive number of computations. Furthermore, the decoder uses a much more complicated symbol MAP decoder. Consequently, the very large constellation size used in ADSL systems makes both conventional bit-level turbo coded QAM and symbol-level turbo TCM very complicated to decode at the receiver end. In other words, conventional bit-level turbo coded QAM and symbol-level turbo TCM both have very high decoding complexity for large ADSL related constellations. These techniques are described in S. Benedetto, D. Divsalar, G. Montorsi and F. Pollara, “Parallel Concatenated Trellis Coded Modulation”, IEEE ICC96, 1996, pp. 974–978; L. Bahl, J. Cocke, F. Jelinek and J. Raviv, “Optimum Decoding of Linear Codes for Minimizing Symbol Error Rate”, IEEE Trans. Inform. Theory, vol. IT-20, pp. 284–287, March 1974; J. Hagenauer and P. Hoeher, “A Viterbi Algorithm with Soft-Decision Outputs and Its Application”, IEEE GLOBECOM89, pp. 47.1.1–47.1.7, November 1989; D. Divsalar, “Turbo Codes for PCS Applications”, IEEE ICC95, pp. 54–59, 1996; P. Robertson, “Illuminating the Structure of Parallel Concatenated Recursive Systematic (TURBO) Codes”, IEEE GLOBECOM94, pp. 1298–1303, November 1994; S. Benedetto, D. Divsalar, G. Montorsi and F. Pollara, “Parallel Concatenated Trellis Coded Modulation”, IEEE ICC96, 1996, pp. 974–978; and G. Ungerboeck, “Channel Coding with Multilevel/Phase Signals”, IEEE Trans. Inform. Theory, vol. IT-28, No. 1, January 1982, pp. 55–67.
A need therefore exists for a method and system that will allow for the effective use of turbo coding in ADSL communication systems.